package Sort;

import java.util.Arrays;

import static Sort.Swap.swap;

//快速排序
public class QuickSort {
    public static void main(String[] args) {
        int[] ary={25,15,30,10,50,3,5,60};
        quickSort(ary);
//        partition(ary,0,ary.length-1);
        System.out.println(Arrays.toString(ary));
    }

    public static void quickSort(int[] arr){
        quick(arr,0,arr.length-1);
    }
    public static void quick(int[] arr,int left,int right){
        if(left>=right){
            //退出条件
            return;
        }
        int index=partition(arr,left,right);//得到上次排序得到的pivot位置
        quick(arr,left,index-1);//递归排序index左边元素
        quick(arr,index+1,right);//递归排序index右边元素
    }
    public static int partition(int[] arr,int left,int right){
        int l=left;
        int r=right;
        int temp=arr[right];//将ary[right]记作pivot
        while(l<r){

            while(l<r&&arr[r]>=temp){
                r--;
            }
            while(l<r&&arr[l]<=temp){
                l++;
            }
            swap(arr,l,r);
        }
        //将pivot和r与l相遇位置元素交换
        swap(arr,l,right);
        return l;//返回相遇位置，既此时的pivot位置
    }

}
